package com.zq.solution.algorithm.divideAndConquer;

/**
 * @ClassName BinarySearch 二分查找
 * @Description 二分查找
 * 前提：线性表必须有序
 * 算法说明：在有序数组array[]中，不断将数组的中间值（mid）和被查找的值比较，如果被查找的值等于array[mid],就返回下标mid;
 *   否则，就将查找范围缩小一半。如果被查找的值小于array[mid], 就继续在左半边查找;如果被查找的值大于array[mid],
 *   就继续在右半边查找。 直到查找到该值或者查找范围为空时， 查找结束。
 * 效率说明：递归的二分查找和非递归的二分查找效率都为O(logN)，递归的二分查找更加简洁，便于理解，但是速度会比非递归的慢。
 * @Author ZQ
 * @Date 2020/11/5 9:37
 * @Version V1.0
 **/
public class BinarySearch {
    public static int binarySearch(int[] a, int key){//递归实现
        return binary(a,key,a.length -1 ,0);
    }
    public static int binary(int[] a, int key, int high, int low){//递归实现
        int mid = low + (high - low) / 2;
        if (low <= high){
            if (key == a[mid]) return mid;
            if (key < a[mid]) return binary(a,key,mid -1, low);
            if (key > a[mid]) return binary(a,key,high,mid + 1);
        }
        return -1;
    }

    public static int findTwoPoint(int[] array,int key){//非递归实现
        int start = 0;
        int last = array.length-1;
        while(start <= last){
            int mid = (last-start)/2+start;//防止直接相加造成int范围溢出
            if(key == array[mid]){//查找值等于当前值，返回数组下标
                return mid;
            }
            if(key > array[mid]){//查找值比当前值大
                start = mid+1;
            }
            if(key < array[mid]){//查找值比当前值小
                last = mid-1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] a = new int[]{1,3,5,7,15,26,37,48,59,100};
        System.out.println(binarySearch(a,15));
    }
}
